package examination_practice01;

import java.util.Arrays;

public class HamiltonianCycle {
    private int V;//图中结点的数量
    private  int[] path;//存储路径
    private int[][] graph;//图的邻接矩阵

    //初始化图
    public HamiltonianCycle(int[][] graph){
        this.graph=graph;
        this.V=graph.length;
        this.path=new int[V];
        Arrays.fill(path,-1);
    }

    //递归、遍历所有可能的结点顺序
    public void hamiltonian(int[] path,int pos){
        if (pos==V){
            if (graph[path[pos-1]][path[0]]==1){
                //prinPath(path);
            }
            return;
        }
        for (int v = 1;v<V;v++){
            if (isValid(v,path,pos)){
                path[pos]=v;
                hamiltonian(path,pos+1);
                path[pos]=-1;
            }
        }
    }

    //判断当前结点是否可以添加到路径中
    public boolean isValid(int v,int[] path,int pos){
        if (graph[path[pos-1]][v]==0){
            return false;
        }
        for (int i=0;i<pos;i++){
            if (path[i]==v){
                return false;
            }
        }
        return true;
    }
}

